1. Field of the Invention
The present invention relates to a cryptographic system and, more particularly, to a method of countering side-channel attacks on an elliptic curve cryptosystem (ECC), which extends a definition field of an elliptic curve of the ECC to an extension in a finite field so as to counter power attacks and fault injection attacks on the ECC using a single algorithm.
2. Description of the Related Art
The protection of private information using cryptographic algorithms and cryptographic protocols is becoming increasingly desirable and important in our information based society. The elliptic curve cryptosystem (ECC) is increasingly being used in practice due to its shorter key sizes and efficient realizations. However, ECC is also known to be vulnerable to various side channel attacks, including power attacks and fault injection attacks. A “public key” algorithm represented by an elliptic curve cryptosystem (ECC) solves the key distribution problem and the electronic signature problem of secret key cryptographic algorithms and has been widely applied to many fields including personal computer data security, Internet based data and financial networks.
The ECC is widely used for smart cards and electronic signatures because the ECC can secure high stability even with a relatively small key size. The ECC is an encoding/decoding system based on a special addition function based on a mathematical and geometrical object called an elliptic curve. In the ECC, an arbitrary elliptic curve E and a point P on the elliptic curve E are selected as system parameters. A person X who wants to encrypt a communication randomly generates an integer d and multiplies the integer d by the point P to generate public key Q (=d*P). Person X publishes Q as a public key and safely stores d as his secret key. Person Y who wants to secretly transmit a message M to person X randomly generates an integer k and multiplies the integer k by the point P to generate A (=k*P). Then, person Y generates B (=M+k*Q) using the public key Q and the message M and transmits a final ciphertext (A,B) to person X. Person X who receives the ciphertext (A,B) calculates d*A using the secret key d, and then performs an arithmetic operation represented by the following Equation 1 so as to restore the message M:M=B−d*A  [Equation 1]
Accordingly, the most important arithmetic operation in ECC is the multiplication d*P. Here, the multiplication d*P can be achieved according to addition and doubling operations on an elliptic curve.
The elliptic curve that is a basis of the operation of ECC will now be explained.
For involution of a prime, q, Fq represents a finite field F having elements q. An elliptic curve E over Fq includes a point at infinity O and is a set of points satisfying the nonsingular Weierstrass equation of Equation 2:y2+a1*x*y+a3*y=x3+a2*x2+a4*x+a6, aiεFq  [Equation 2]
In mathematics, more specifically in abstract algebra, field extensions are the main object of study in field theory. The general idea is to start with a base field and construct in some manner a larger field which contains the base field and satisfies additional properties. Field extensions can be generalized to ring extension which consists of a ring and one of its subrings. A field extension is a special case of ring extension. In mathematics, more specifically in ring theory, a ring extension or extension ring is a ring R with a subring S. We write R/S and say R is a ring extension of S. For a random extension field K of Fq (see Equation 2), E(K) is defined as a subset of E which includes rational elliptic curve points, as represented by the following Equation 3 wherein E(K) is represented as E for convenience of explanation:E(K)={(x,y)εE|x,yεK}∪{Q}  [Equation 3]
As well known in the art, E(K) forms an Abelian group for a specific addition formula. In mathematics, an Abelian group, also called a commutative group, is a group (G, *) with the additional property that the group operation * is commutative, so that for all a and b in G, a*b=b*a. Abelian groups are named after Norwegian mathematician Niels Henrik Abel. Groups in which the group operation is not commutative are called non-Abelian (or non-commutative). Group operation in an Abelian group is commutative as well as associative. For example, it is known that Equation 2 can be transformed to the following Equation 4 using an appropriate elliptic curve isomorphism if q is involution of 2 and the elliptic curve E is not a supersingular elliptic curve.y2+x*y=x3+a*x2+b,a,bεFq  [Equation 4]
It is assumed that the point at infinity O functions as an identity element and two points P and Q that satisfy Equation 4 satisfy Equation 5:P=(x1,y1)εE(K)−{O}Q=(x2,y2)εE(K)−{O,−P}  [Equation 5]
Under the condition of Equation 5, the inverse element −P of the point P is defined as −P=(x1, x1+y1) for the two points P and Q satisfying Equation 4 and P+Q (=x3, y3) is represented by Equations 6 and 7. Here, Equation 6 below defines an addition formula when P and Q are different from each other and Equation 7 below defines an addition formula when P and Q are equal to each other.x3=((y1+y2)/(x1+x2))2+(y1+y2)/(x1+x2)+x1+x2+a y3=((y1+y2)/(x1+x2))*(x1+x3)+x3+y1  [Equation 6]x3=x12b/x12 y3=x12+(x1+y1/x1)*x3+x3  [Equation 7]
Addition formulas for other elliptic curves can be found in Reference [17]. In the operation of ECC, one of the arithmetic operations that requires a long period of time is scalar multiplication. If k is a positive integer and P is a point on an elliptic curve E, scalar multiplication k*P means the addition of P k times and (−k)*P means addition of −P k times. ECC is explained in more detail in References [13] and [19].
Although ECC has the aforementioned advantages, it is well known that ECC is vulnerable to various side-channel attacks including power attacks and fault injection attacks. In cryptography, a “side channel attack” is any attack based on information gained from the physical implementation of a cryptosystem, rather than theoretical weaknesses in the algorithms (compare cryptanalysis). For example, timing information, power consumption, electromagnetic leaks or even sound can provide an extra source of information that can be exploited to break the cryptosystem and decode the encrypted information. Many side-channel attacks require considerable technical knowledge of the internal operation of the system on which the cryptography is implemented. The power monitoring attacks and fault injection attacks are generally explained below.
The power monitoring side-channel attacks were firstly described by Kocher et al. (Refer Reference [14]). The power monitoring attacks extract secret information from power (e.g., electrical current) consumption and/or heat generation of a microprocessor while being used to implement cryptosystem. Power consumption attacks on ECC, which are known to include a simple power attack (SPA), a differential power attack (DPA), a refined power-analysis attack (RPA), a zero-value point attack (ZPA) and a doubling attack.
The SPA observes power consumption signals with respect to a single execution of cryptography and classifies various fundamental crypto operations (For example, addition and doubling operations in ECC) from the power consumption signals. Examining graphs of time against current used by a device can often show exactly what the device is doing at a given point. Accordingly, Double-and-Add Always method and Montgomery powering ladder algorithm are used as countermeasures against the SPA. The Double-and-Add Always method is explained in detail in Reference [7] and the Montgomery powering ladder algorithm is explained in detail in References [12]. [15] and [20].
The DPA collects power consumption data and obtains useful information from the power consumption data using a statistical tool. Random blinding techniques are used as countermeasures for the DPA. The random blinding techniques include a random exponent blinding method, a random message blinding method and random point representation. However, the random blinding techniques are vulnerable to power attacks such as RPA and ZPA. The random blinding techniques are described in detail in Reference [7].
Furthermore, a random elliptic curve isomorphism method, a random field isomorphism method, a 2P* method and a multiplier randomization method are also used as countermeasures for the DPA. However, the random elliptic curve isomorphism method, random field isomorphism method, and 2P* method are vulnerable to RPA and ZPA and the multiplier randomization method has low memory efficiency. The random elliptic curve isomorphism method and random field isomorphism method are explained in detail in Reference [11] and the 2P* method and multiplier randomization method are described in detail in Reference [6].
The RPA uses the feature that processing for points having a zero coordinate and processing for other (non-zero) points have different power consumption profiles. The RPA selects a specific point having the zero coordinate, and then inputs a point that is equal to the specific point when multiplied by a specific scalar to a device (system) so as to perform a power attack. Though the ZPA is similar to the RPA, the ZPA does not use zero coordinates and uses a zero-value register.
Both the RPA and ZPA operate only when intermediate results of scalar multiplication algorithms can be supposed partially or entirely. Accordingly, the RPA and ZPA can be prevented if appropriate message and/or exponent randomization techniques are applied to scalar multiplication algorithms. The RPA and ZPA are respectively described in detail in References [9] and [1].
The doubling attack attacks a cryptosystem based on the assumption that an adversary can find whether two intermediate result values of two different arithmetic operations are identical to each other. Accordingly, the doubling attack can be prevented if appropriate message and/or exponent randomization techniques are used. The doubling attack is described in detail in Reference [8].
The fault injection attack (refer to References [2]. [4] and [5]) is a very powerful cryptosystem attack technique. The fault injection attack injects an intentional fault into a cryptosystem and analyzes a fault result to obtain significant information. Accordingly, a general countermeasure for the fault injection attack is to check validity of input values or output values. Specifically, whether a fault is injected into ECC is checked by determining whether input points and output points of an elliptic curve scalar multiplication algorithm satisfy an elliptic curve equation in the ECC.
Another powerful countermeasure to the fault injection attack, proposed by Shamir and applied to an RSA cryptosystem, is herein generally explained. Person A who wants to perform cryptography communication generates two large primes p and q and calculates N (=p×q) and φ(n) {=(p−1)×(q−1)} using the two primes p and q. Then, person A selects an integer e which is relatively prime for φ(n) and generates an integer d that satisfies Equation 8. Here, relatively prime means the relationship between two natural numbers having only one common factor, “1”. For example, 8 and 9 are relatively prime because factors of 8 are 1, 2, 4 and 8 and factors of 9 are 1, 3 and 9.ed=1 mod φ(n)  [Equation 8]
Equation 8 is a modular equation that represents that the remainder of a division of ed by φ(n) is 1. In mathematics, a modular equation is an algebraic equation satisfied by moduli, in the sense of moduli problem. That is, given a number of functions on a moduli space, a modular equation is an equation holding between them, or in other words an identity for moduli. The most frequent use of the term modular equation is in relation with the moduli problems for elliptic curves. In the case of elliptic curves, there is one modulus, so moduli spaces are algebraic curves. The modulus of the elliptic integral therefore was probably the first modulus to be recognized. Thus, the equation of a modular (elliptic) curve is a modular equation.
An elliptic curve can be represented by several sets of coordinates. The addition formula, which is defined by setting a point at infinity O to zero, differs for each coordinate: the computation amount of addition differs for each coordinate. Two coordinates, affine coordinates and projective coordinates, are well known. Affine coordinate requires a division in every addition and every doubling but requires fewer multiplications than projective coordinate.
Another coordinate is called jacobian coordinate. The addition formula in jacobian coordinates does not require any division modulo p in either addition or doubling and requires a division only once in the final stage of the computation of elliptic curve exponentiation.
Referring to the above modular Equation 8, person A publishes N and e as his public key and safely stores p, q and d as his secret keys. Person B who wants to transmit an encrypted message m transmits a ciphertext C corresponding to a result of a modular exponentiation operation represented by the following Equation 9 using the public key (N, 3) of person A.C=me mod N  [Equation 9]
Person A who receives the ciphertext C from person B performs a modular exponentiation represented by the following Equation 10 using his secret key d to restore the original message m (plaintext).M=Ca mod N  [Equation 10]
Accordingly, the most important operation in an RSA public key cryptosystem is the modular exponentiation that calculates me mod N or Ca mod N. Here, to safely insulate the calculation of Equation 9 or Equation 10 from the fault injection attack, the Shamir method selects a sufficiently small arbitrary prime r and calculates mp′ and mq′.mp′=md mod(p-1)*(r-1) mod p*r mq′=md mod(q-1)*(r-1) mod q*r  [Equation 11]
Subsequently, the Shamir method checks whether mp′=mq′ mod r. Then, the plaintext m represented by Equation 10 can be easily obtained using Chinese remainder theorem (CRT). Reference [18] explains the RSA cryptosystem in detail.
A sign change fault attack has been recently proposed as a new fault injection attack. The sign change fault attack changes only the sign (positive/negative) of the coordinate of an intermediate result value of a scalar multiplication of an ECC so as to avoid the point validity judgment that serves as a countermeasure against general fault injection attacks. To counter the sign change fault attack, a method of performing two ECC scalar multiplications was proposed. However, this method deteriorates system performance. The sign change fault attack is described in detail in Reference [4].
As described above, the methods for countering the power attacks and fault injection attacks on an ECC have problems in terms of security and performance, cannot cope with simultaneous power attacks and the fault injection attacks, or cause system performance deterioration when countering the sign change fault attack.